#define _CRT_SECURE_NO_WARNINGS
#include "heap.h"
// 堆的构建
void HeapInit(Heap* hp)
{
	assert(hp);

	hp->a = NULL;
	hp->size = hp->capacity = 0;

}
void HeapPrint(Heap* hp)
{
	assert(hp);

	for (int i = 0; i < hp->size; ++i)
	{
		printf("%d ", hp->a[i]);
	}
	printf("\n");
}

//调整为堆
//左孩子的节点:   2i + 1
//右孩子的节点 : 2i + 2
//父亲节点 : (i - 1) / 2
void Adjustup(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (a[parent] > a[child] && child > 0)
	{
		Swap(&a[parent],&a[child]);
		child = parent;
		parent = (child - 1) / 2;
	}
}
void Adjustdown(Heap* hp, int child);

//交换函数
void Swap(HPDataType* a, HPDataType* b)
{
	HPDataType tmp = *a;
	*a = *b;
	*b = tmp;
}

// 堆的销毁
void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->a);
	hp->capacity = hp->size = 0;
}

// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);

	if (hp->size == hp->capacity)
	{
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(hp->a,newcapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc failed!");
			exit(-1);
		}
		hp->a = tmp;
		hp->capacity = newcapacity;

	}

	hp->a[hp->size] = x;
	hp->size++;
	Adjustup(hp->a, hp->size - 1);

}
//向下调整
void Adjustdown(HPDataType* a, int parent, int size)
{
	int  leftchild = 2 * parent + 1;


	while ( leftchild < size)
	{

		if (leftchild + 1 < size && a[leftchild] > a[leftchild + 1])
		{
			leftchild += 1;
		}


		if (a[parent] > a[leftchild])
		{
			Swap(&a[parent], &a[leftchild]);
			parent = leftchild;
			leftchild = 2 * parent + 1;

		}
		else
		{
			break;
		}

	}

}

// 堆的删除
void HeapPop(Heap* hp)
{
	assert(hp);

	Swap(&hp->a[0], &hp->a[hp->size-1]);
	hp->size--;

	Adjustdown(hp->a, 0, hp->size);


}

// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(HeapEmpty);
	return hp->a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{
	return hp->size;
}


// 堆的判空
bool HeapEmpty(Heap* hp)
{
	assert(hp);

	return hp->size == 0;
}
